package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _11_判断t1树中是否有与t2树拓扑结构完全相同的子树 {

    public static boolean isSubTree(TreeNode t1, TreeNode t2) {

        boolean result = check(t1, t2);

        if (t1 == null || result) {

            return result;
        }

        return isSubTree(t1.left,t2) || isSubTree(t1.right,t2);
    }

    public static boolean check(TreeNode t1,TreeNode t2) {

        if (t1 == null && t2 == null) {

            return true;
        }

        if (t1 == null && t2 != null) {

            return false;
        }

        if (t2 == null && t1 != null) {

            return false;
        }

        if (t1.val != t2.val) {

            return false;
        }

        return check(t1.left,t2.left) && check(t1.right, t2.right);
    }

    public static void main(String[] args) {

        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.left.left = new TreeNode(4);
        t1.left.left.left = new TreeNode(8);
        t1.left.left.right = new TreeNode(9);
        t1.left.right = new TreeNode(5);
        t1.left.right.left = new TreeNode(10);
        t1.right = new TreeNode(3);
        t1.right.left = new TreeNode(6);
        t1.right.right = new TreeNode(7);

//        TreeNode t2 = new TreeNode(2);
//        t2.left = new TreeNode(4);
//        t2.left.left = new TreeNode(8);
//        t2.right = new TreeNode(5);

        TreeNode t2 = new TreeNode(3);
        t2.left = new TreeNode(6);
//        t2.left.left = new TreeNode(8);
        t2.right = new TreeNode(7);

        boolean result = isSubTree(t1, t2);
        System.out.println(result);

    }
}

